//给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充
//。
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X"
//,"X"]]
//输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
//解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都
//会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
// 
//
// 示例 2： 
//
// 
//输入：board = [["X"]]
//输出：[["X"]]
// 
//
// 
//
// 提示： 
//
// 
// m == board.length 
// n == board[i].length 
// 1 <= m, n <= 200 
// board[i][j] 为 'X' 或 'O' 
// 
// 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 
// 👍 559 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    boolean[][] bl;
    char[][] board;
    int yLen, xLen;
    public void solve(char[][] board) {
        this.board = board;
        this.yLen = board.length;
        this.xLen = board[0].length;
        this.bl = new boolean[yLen][xLen];

        //邻边与跟邻边相连的bl置为true;
        for (int i = 0; i < xLen; i++) {
            setTrue(0, i);
            setTrue(yLen-1, i);
        }

        for (int i = 1; i < yLen -1; i++) {
            setTrue(i, 0);
            setTrue(i, xLen-1);
        }


        //循环调用数组，把bl为false与内容为O的置为X

        for (int i = 1; i < xLen -1; i++) {
            for (int j = 1; j < yLen - 1; j++) {
                setX(j, i);
            }
        }
    }

    private void setTrue(int y, int x) {
        if (x < 0 || x >= xLen || y < 0 || y >= yLen) {
            return;
        }
        if (bl[y][x]) {
            return;
        }
        boolean temp = bl[y][x];
        bl[y][x] = true;
        if (board[y][x] == 'O' && !temp) {
            setTrue(y+1, x);
            setTrue(y-1, x);
            setTrue(y, x+1);
            setTrue(y, x-1);
        }
    }

    private void setX(int y, int x) {
        if (x < 0 || x >= xLen || y < 0 || y >= yLen) {
            return;
        }
        if (bl[y][x]) {
            return;
        }
        char temp = board[y][x];
        board[y][x] = 'X';
        if (temp == 'O') {
            setX(y+1, x);
            setX(y-1, x);
            setX(y, x+1);
            setX(y, x-1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
